package homework2.NearestPoints;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

import homework2.NearestPoints.Point.SIGH;

/**
 * Nearest Points calculation class. And there is no points with the same x- and
 * y- coordinate allowed
 * 
 * @author eDisOn 2009212634 lilh09@mails.tsinghua.edu.cn
 * 
 */
public class CalcNearestPoints
{
	Point[] points = null;

	public CalcNearestPoints()
	{

	}

	public ArrayList<NearestPoints> exec(ArrayList<Point> initPoints)
	{
		Collections.sort(initPoints, new Comparator<Point>()
		{
			public int compare(Point firPoint, Point secPoint)
			{
				if (firPoint.x < secPoint.x)
				{
					return -1;
				}
				else if (firPoint.x > secPoint.x)
				{
					return 1;
				}
				else
				{
					return 0;
				}
			}
		});

		points = new Point[initPoints.size()];
		for (int i = 0; i < points.length; i++)
		{
			points[i] = initPoints.get(i);
		}
		return findNearestPoints(points, 0, points.length - 1);
	}

	private ArrayList<NearestPoints> findNearestPoints(Point[] points,
			int start, int end)
	{
		ArrayList<NearestPoints> nearestPointsArray = null;

		/**************** BASE CASE ****************/
		if (start == end)
		{
			nearestPointsArray = new ArrayList<NearestPoints>();
			NearestPoints nearestPoints = new NearestPoints(points[start],
					points[end], Integer.MAX_VALUE);
			nearestPointsArray.add(nearestPoints);
		}

		/**************** RECURSION PROCESS ****************/
		else if (start < end)
		{

			/*************** 0.Divide and conquer subproblems ***************/
			int mid = (start + end) >> 1;
			Point splitPoint = points[mid];
			ArrayList<NearestPoints> leftNPArray = findNearestPoints(points,
					start, mid);
			ArrayList<NearestPoints> rightNPArray = findNearestPoints(points,
					mid + 1, end);

			/*************** 1.Find nearest points distance in two separated points zones ***************/
			double minDist = Integer.MAX_VALUE;
			double leftMinDist = leftNPArray.get(0).distance;
			double rightMinDist = rightNPArray.get(0).distance;
			if (leftMinDist < rightMinDist)
			{
				minDist = leftMinDist;
				nearestPointsArray = leftNPArray;
//				for (NearestPoints np : leftNPArray)
//				{
//					nearestPointsArray.add(np);
//				}
			}
			else if (leftMinDist > rightMinDist)
			{
				minDist = rightMinDist;
				nearestPointsArray = rightNPArray;
//				for (NearestPoints np : rightNPArray)
//				{
//					nearestPointsArray.add(np);
//				}
			}
			else
			{
				minDist = leftMinDist;// leftMinDist == rightMinDist
				
				nearestPointsArray = leftNPArray;
				nearestPointsArray.addAll(rightNPArray);
				
//				for (NearestPoints np : leftNPArray)
//				{
//					nearestPointsArray.add(np);
//				}
//				for (NearestPoints np : rightNPArray)
//				{
//					nearestPointsArray.add(np);
//				}
			}

			/*************** 2.Calculate nearest points between two zones ***************/

			/*
			 * 2.1 - Merge two sorted points array according to Y coordinate
			 * value, add set the SIGH(LEFT or RIGHT) to each points according
			 * to their zone's sigh
			 */
			ArrayList<Point> leftTmpPoints = new ArrayList<Point>();
			ArrayList<Point> rightTmpPoints = new ArrayList<Point>();
			for (int i = start; i < mid + 1; i++)
			{
				Point point = points[i];
				point.sigh = SIGH.LEFT;
				leftTmpPoints.add(point);
			}
			for (int i = mid + 1; i < end + 1; i++)
			{
				Point point = points[i];
				point.sigh = SIGH.RIGHT;
				rightTmpPoints.add(point);
			}

			int leftIndex = 0, rightIndex = 0, index = start;
			while (leftIndex < leftTmpPoints.size()
					&& rightIndex < rightTmpPoints.size())
			{
				Point leftPoint = leftTmpPoints.get(leftIndex);
				Point rightPoint = rightTmpPoints.get(rightIndex);
				if (leftPoint.y <= rightPoint.y)
				{
					points[index] = leftPoint;
					leftIndex++;
				}
				else
				{
					points[index] = rightPoint;
					rightIndex++;
				}
				index++;
			}
			if (leftIndex == leftTmpPoints.size())
			{
				while (rightIndex < rightTmpPoints.size())
				{
					points[index] = rightTmpPoints.get(rightIndex);
					rightIndex++;
					index++;
				}
			}
			else
			{
				while (leftIndex < leftTmpPoints.size())
				{
					points[index] = leftTmpPoints.get(leftIndex);
					leftIndex++;
					index++;
				}
			}

			/*
			 * 2.2 - find neighbor points in the (2 * minDist) zones
			 */
			ArrayList<Point> neighborPoints = new ArrayList<Point>();
			for (int i = start; i <= end; i++)
			{
				Point currentPoint = points[i];
				if (Math.abs(splitPoint.x - currentPoint.x) <= minDist)
				{
					neighborPoints.add(currentPoint);
				}
			}

			/*
			 * 2.3 - calculate nearest points via bottom up method according to
			 * points' Y coordinate.
			 */
			double distBTW;

			// Because the end point have been calculated distance with another
			// neighbor in previous iteration process, so the terminate
			// condition is pos < end instead of pos <= end.
			for (int pos = 0; pos < neighborPoints.size(); pos++)
			{
				Point point = neighborPoints.get(pos);
				for (int neighbor = 1; neighbor < 7; neighbor++)
				{
					int neighborPosition = pos + neighbor;

					// judge whether neighbor reaches the points zone's end
					if (neighborPosition > neighborPoints.size() - 1)
					{
						break;
					}

					// if point and its neighborPoint are not from same zone,
					// then calculate the distance between them
					Point neighborPoint = neighborPoints.get(neighborPosition);
					if (isFromSameZone(point, neighborPoint))
					{
						continue;
					}
					else
					{
						distBTW = calcDistance(point, neighborPoint);

						// If distance of points between two zones is less than
						// minDist, then clear up nearestPointsArray and add
						// this points pair into nearestPointsArray
						if (distBTW < minDist)
						{
							minDist = distBTW;
							nearestPointsArray.clear();
							nearestPointsArray.add(new NearestPoints(point,
									neighborPoint, minDist));
						}
						else if (distBTW == minDist)
						{
							nearestPointsArray.add(new NearestPoints(point,
									neighborPoint, minDist));
						}
						else
						{
							// DO NOTHING!!!
						}
					}
				}
			}
		}
		return nearestPointsArray;
	}

	private double calcDistance(Point firPoint, Point secPoint)
	{
		return Math.sqrt(Math.pow(firPoint.x - secPoint.x, 2)
				+ Math.pow(firPoint.y - secPoint.y, 2));
	}

	private boolean isFromSameZone(Point firPoint, Point secPoint)
	{
		if (firPoint.sigh == secPoint.sigh)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	public String getResult(ArrayList<NearestPoints> nearestPointsArr)
	{
		int index = 1;
		String display = "";
		display += "There are " + nearestPointsArr.size()
				+ " pair/pairs nearest points exist.\n";
		display += "Minimum distance is : " + nearestPointsArr.get(0).distance
				+ "\n";
		for (NearestPoints nearestPoints : nearestPointsArr)
		{
			display += index++ + ".Points:(" + nearestPoints.firPoint.x + ","
					+ nearestPoints.firPoint.y + ") & ("
					+ nearestPoints.secPoint.x + "," + nearestPoints.secPoint.y
					+ ")";
			display += "\n";
		}
		return display;
	}

	public static void main(String args[])
	{
		ArrayList<Point> points = new ArrayList<Point>();
		points.add(new Point(2, 2));
		points.add(new Point(4, 1));
		points.add(new Point(3, 3));
		points.add(new Point(3, 1));
		points.add(new Point(4, 4));
		points.add(new Point(4, 3));
		points.add(new Point(3, 2));
		points.add(new Point(4, 2));
		points.add(new Point(2, 1));
		points.add(new Point(1, 1));

		CalcNearestPoints calc = new CalcNearestPoints();
		calc.exec(points);
	}
}

class NearestPoints
{
	Point firPoint, secPoint;
	double distance;

	public NearestPoints(Point initFirPoint, Point initSecPoint,
			double initDistance)
	{
		firPoint = initFirPoint;
		secPoint = initSecPoint;
		distance = initDistance;
	}

	public void setNearestPoints(Point nuFirPoint, Point nuSecPoint)
	{
		firPoint = nuFirPoint;
		secPoint = nuSecPoint;
	}
}

class Point
{
	int x;
	int y;

	public SIGH sigh;

	public enum SIGH
	{
		LEFT, RIGHT
	};

	public Point(int initX, int initY)
	{
		x = initX;
		y = initY;
	}
}

class Line
{
	Point firPoint, secPoint;

	public Line(Point initFirPoint, Point initSecPoint)
	{
		firPoint = initFirPoint;
		secPoint = initSecPoint;
	}
}